package org.example.heap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 力扣堆类型题
 * @Author chaigq
 * @Date 2020/11/16 7:00 上午
 * @Version 1.0
 */
public class LeetCodeHeap {


    /**
     * 给你一个链表数组，每个链表都已经按升序排列。
     *
     *  请你将所有链表合并到一个升序链表中，返回合并后的链表。
     *
     *  示例 1：
     *  输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     *   1->4->5,
     *   1->3->4,
     *   2->6
     * ]
     * 将它们合并到一个有序链表中得到。
     * 1->1->2->3->4->4->5->6
     *
     *  示例 2：
     *  输入：lists = []
     * 输出：[]
     *
     *  示例 3：
     *  输入：lists = [[]]
     * 输出：[]
     *
     *  提示：
     *  k == lists.length
     *  0 <= k <= 10^4
     *  0 <= lists[i].length <= 500
     *  -10^4 <= lists[i][j] <= 10^4
     *  lists[i] 按 升序 排列
     *  lists[i].length 的总和不超过 10^4
     *
     *  Related Topics 堆 链表 分治算法
     */
    // Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    // TODO 顺序合并，基于连个链表的合并来进行
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; i ++){
            ans = twoLists(ans, lists[i]);
        }
        return ans;
    }

    // TODO 解决问题的核心方法
    // TODO 如何合并两个有序链表？假设链表 a 和 b 的长度都是 n，如何在 O(n) 的时间代价以及 O(1) 的空间代价完成合并？
    // 这个问题在面试中常常出现，为了达到空间代价是 O(1)O(1)，我们的宗旨是「原地调整链表元素的 next 指针完成合并」
    //
    public ListNode twoLists(ListNode a, ListNode b) {
        if (a == null || b == null) return a != null ? a : b;
        ListNode head = new ListNode(0);
        ListNode res = head, aCopy = a, bCopy = b;
        while (aCopy != null && bCopy != null){
            if (aCopy.val < bCopy.val){
                res.next = aCopy;
                aCopy = aCopy.next;
            }else {
                res.next = bCopy;
                bCopy = bCopy.next;
            }
            res = res.next;
        }
        res.next = (aCopy != null ? aCopy : bCopy);
        return head.next;
    }
    // =======================================================================================================
    // TODO 分治合并解决
    public ListNode mergeKLists2(ListNode[] lists) {

        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] listNodes, int start, int end){

        if (start == end) return listNodes[start];
        if (start > end) return null;
        int mid = (start + end) / 2;
        return twoLists(merge(listNodes, start, mid), merge(listNodes, mid + 1, end));
    }

    /**
     * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后倒数第 k 个最大的元素，而不是第 k 个不同的元素。
     *
     *  示例 1:
     *
     *  输入: [3,2,1,5,6,4] 和 k = 2
     * 输出: 5
     *
     *
     *  示例 2:
     *
     *  输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
     * 输出: 4
     *
     *  说明:
     *
     *  你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
     *  Related Topics 堆 分治算法
     *
     *  TODO 这里主要考察的是Java中的排序算法，这里将排序算法一一列举出来
     */
    public int findKthLargest(int[] nums, int k) {
        int[] res = sortNums(nums);
        return res[res.length - k];
    }
    // 排序方法需要慢慢的补充进来
    public int[] sortNums(int[] nums) {
        // TODO 冒泡排序

        //for (int i = 0; i < nums.length; i ++){
        //    for (int j = 0; j < nums.length - 1 - i; j ++){
        //        if (nums[j + 1] < nums[j]){
        //            int temp = nums[j + 1];
        //            nums[j + 1] = nums[j];
        //            nums[j] = temp;
        //        }
        //    }
        //}

        // TODO 选择排序
//        for (int i = 0; i < nums.length; i ++){
//            int index = i;
//            for (int j = i + 1; j < nums.length; j ++){
//                if (nums[j] < nums[index]){
//                    index = j;
//                }
//            }
//            int temp = nums[i];
//            nums[i] = nums[index];
//            nums[index] = temp;
//        }

        // TODO 插入排序


        return nums;
    }

    /**
     * 城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图A）上显示的所有建筑物的位置和高度，请编写一个程序以输出由
     * 这些建筑物形成的天际线（图B）。
     *
     * 每个建筑物的几何信息用三元组 [Li，Ri，Hi] 表示，其中 Li 和 Ri 分别是第 i 座建筑物左右边缘的 x 坐标，Hi 是其高度。可以保证
     * 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX 和 Ri - Li > 0。您可以假设所有建筑物都是在绝对平坦且高度为 0 的表面上的
     * 完美矩形。
     *
     *  例如，图A中所有建筑物的尺寸记录为：[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] 。
     *
     *  输出是以 [ [x1,y1], [x2, y2], [x3, y3], ... ] 格式的“关键点”（图B中的红点）的列表，它们唯一地定义了天际线。关键点
     * 是水平线段的左端点。请注意，最右侧建筑物的最后一个关键点仅用于标记天际线的终点，并始终为零高度。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
     *
     *  例如，图B中的天际线应该表示为：[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]。
     *
     *  说明:
     *  任何输入列表中的建筑物数量保证在 [0, 10000] 范围内。
     *  输入列表已经按左 x 坐标 Li 进行升序排列。
     *  输出列表必须按 x 位排序。
     *  输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答案；三
     * 条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]
     *
     *  TODO Related Topics 堆 树状数组 线段树 分治算法 Line Sweep
     */
    public List<List<Integer>> getSkyline(int[][] buildings) {

        if (buildings.length == 0) return new ArrayList<>();

        return mergeSkylines(buildings, 0, buildings.length - 1);
    }
    public List<List<Integer>> mergeSkylines(int[][] buildings, int start, int end) {
        List<List<Integer>> res = new ArrayList<>();
        //只有一个建筑, 将 [x, h], [y, 0] 加入结果
        if (start == end) {
            List<Integer> temp = new ArrayList<>();
            // x坐标值
            temp.add(buildings[start][0]);
            // h坐标值
            temp.add(buildings[start][2]);
            res.add(temp);

            temp = new ArrayList<>();
            // y坐标值
            temp.add(buildings[start][1]);
            // 0坐标值
            temp.add(0);
            res.add(temp);
            return res;
        }
        int mid = (start + end) / 2;

        //第一组解
        List<List<Integer>> Skyline1  = mergeSkylines(buildings, start, mid);
        //第二组解
        List<List<Integer>> Skyline2  = mergeSkylines(buildings, mid + 1, end);

        //下边将两组解合并
        int h1 = 0;
        int h2 = 0;
        int i = 0;
        int j = 0;
        while (i < Skyline1 .size() || j < Skyline2 .size()) {
            // 第一组 坐标
            long x1 = i < Skyline1 .size() ? Skyline1 .get(i).get(0) : Long.MAX_VALUE;
            // 第二组 坐标
            long x2 = j < Skyline2 .size() ? Skyline2 .get(j).get(0) : Long.MAX_VALUE;
            long x = 0;
            //比较两个坐标
            if (x1 < x2) {
                h1 = Skyline1 .get(i).get(1);
                x = x1;
                i++;
            } else if (x1 > x2) {
                h2 = Skyline2 .get(j).get(1);
                x = x2;
                j++;
            } else {
                // x1 和 x2 相等
                h1 = Skyline1 .get(i).get(1);
                h2 = Skyline2 .get(j).get(1);
                x = x1;
                i++;
                j++;
            }
            //更新 height
            int height = Math.max(h1, h2);
            //重复的解不要加入
            if (res.isEmpty() || height != res.get(res.size() - 1).get(1)) {
                List<Integer> temp = new ArrayList<>();
                temp.add((int) x);
                temp.add(height);
                res.add(temp);
            }
        }
        return res;
    }

    /**
     * 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     *
     *  返回滑动窗口中的最大值。
     *
     *  进阶：
     *  你能在线性时间复杂度内解决此题吗？
     *
     *  示例:
     *  输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
     * 输出: [3,3,5,5,6,7]
     * 解释:
     *
     *   滑动窗口的位置                最大值
     * ---------------               -----
     * [1  3  -1] -3  5  3  6  7       3
     *  1 [3  -1  -3] 5  3  6  7       3
     *  1  3 [-1  -3  5] 3  6  7       5
     *  1  3  -1 [-3  5  3] 6  7       5
     *  1  3  -1  -3 [5  3  6] 7       6
     *  1  3  -1  -3  5 [3  6  7]      7
     *
     *  提示：
     *
     *  1 <= nums.length <= 10^5
     *  -10^4 <= nums[i] <= 10^4
     *  1 <= k <= nums.length
     *
     *  Related Topics 堆 Sliding Window
     *
     */
    // TODO 暴力方法
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];
        int[] output = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i ++){
            int max = 0;
            for (int j = i; j < i + k; j ++){
                max = Math.max(max, nums[j]);
            }
            output[i] = max;
        }
        return output;
    }
    // TODO 双向队列
    public int[] maxSlidingWindow2(int[] nums, int k) {
        return null;
    }

    /**
     * //给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...] (si < ei)，为避免会议冲突，同时要考虑
     * //充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。
     * //
     * // 示例 1:
     * //
     * // 输入: [[0, 30],[5, 10],[15, 20]]
     * //输出: 2
     * //
     * // 示例 2:
     * //
     * // 输入: [[7,10],[2,4]]
     * //输出: 1
     * // Related Topics 堆 贪心算法 排序
     */
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];
        for (int i = 0; i < intervals.length; i ++){
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int startIndex = 0;
        int endIndex = 0;
        int room = 0;
        while (startIndex < intervals.length){
            if (start[startIndex] >= end[endIndex]){
                room -- ;
                endIndex ++;
            }
            room ++;
            startIndex ++;
        }
        return room;
    }













    public static void main(String[] args) {

    }















}
